package leetcode.problems;


import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by gmwang on 2018/7/25
 */
public class _0821FindTheLargestValueInEachTreeRow {
    /**
     * You need to find the largest value in each row of a binary tree.
     * 找到二叉树里的最大值
     * Example:
     * Input:
     *
     *           1
     *          / \
     *         3   2
     *        / \   \
     *       5   3   9
     *      / \ / \ / \
     *     5 3 9  1 2  3
     * Output: [1, 3, 9]
     *
     *           3
     *          / \
     *         1   5
     *        / \  / \
     *       0  2 4  6
     *          \
     *          3
     *
     *   Expected  [3,5,6,3]
     *
     * [3,1,5,0,2,4,6,null,null,null,3]
     *
     * [57,46,89,-36]
     *            57
     *          / \
     *         46  89
     *        /
     *     -36
     *
     *   Expected  [57,89,-36]
     *
     *   [-2147483648,-2147483648]
     *
     *             -2147483648
     *            /
     *   -2147483648
     *
     * [-2147483648,-2147483648]
     */
    /**
     * @param root
     * @return
     */
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        list.add(root.val);
        int num = 1;
        largestValuesList(root, list,num);
        return list;
    }

    public List<Integer> largestValuesList(TreeNode root, List<Integer> list,int num) {
        int max = Integer.MIN_VALUE;
        boolean flag = false;
        if (root != null) {
            if (root.left != null) {
                if (root.right != null) {
                    if(((root.left.val > root.right.val) ? root.left.val : root.right.val) == max){
                        flag = true;
                    }else {
                        max = (root.left.val > root.right.val) ? root.left.val : root.right.val;
                    }
                } else {
                    if(max == root.left.val){
                        flag = true;
                    }else {
                        max = root.left.val;
                    }
                }
            }else if(root.right != null){
                if(max == root.right.val){
                    flag = true;
                }else {
                    max = root.right.val;
                }
            }
            if(list.size() > num){
                if(list.get(num) < max){
                    list.remove(num);
                    list.add(num,max);
                }
            }else{
                if(max != Integer.MIN_VALUE ||(max == Integer.MIN_VALUE && flag ))
                list.add(max);
            }
        }
        num++;
        if (root != null) {
            if (root.left != null) {
                largestValuesList(root.left, list,num);
            }
            if (root.right != null) {
                largestValuesList(root.right, list,num);
            }
        }
        return list;
    }

//    public List<Integer> largestValues(TreeNode root) {
//        List<Integer> result = new ArrayList<>();
//        if (root == null) return result;
//
//        Queue<TreeNode> nodeq = new LinkedList<>();
//        nodeq.add(root);
//        while(!nodeq.isEmpty()) {
//            int max=Integer.MIN_VALUE;
//            Queue<TreeNode> childNodes = new LinkedList<>();
//            childNodes.addAll(nodeq);
//            nodeq.clear();
//            while(!childNodes.isEmpty()) {
//                TreeNode n = childNodes.poll();
//                max=Math.max(max,n.val);
//                if(n.left != null) nodeq.add(n.left);
//                if(n.right != null) nodeq.add(n.right);
//            }
//            result.add(max);
//        }
//        return result;
//    }


    @Test
    public void test() {
//        TreeNode treeNode1 = new TreeNode(1);
//        TreeNode treeNode1L = new TreeNode(3);
//        TreeNode treeNode1R = new TreeNode(2);
//        TreeNode treeNode1LL = new TreeNode(5);
//        TreeNode treeNode1LR = new TreeNode(3);
//        TreeNode treeNode2R = new TreeNode(9);
//        treeNode1.left = treeNode1L;
//        treeNode1.right = treeNode1R;
//        treeNode1L.left = treeNode1LL;
//        treeNode1L.right = treeNode1LR;
//        treeNode1R.right = treeNode2R;
//        TreeNode treeNode1LLL = new TreeNode(5);
//        TreeNode treeNode1LLR = new TreeNode(3);
//        TreeNode treeNode1RLL = new TreeNode(9);
//        TreeNode treeNode1RLR = new TreeNode(1);
//        TreeNode treeNode1RRL = new TreeNode(2);
//        TreeNode treeNode1RRR = new TreeNode(3);
//        treeNode1LL.left = treeNode1LLL;
//        treeNode1LL.right = treeNode1LLR;
//        treeNode1LR.left = treeNode1RLL;
//        treeNode1LR.right = treeNode1RLR;
//        treeNode2R.left = treeNode1RRL;
//        treeNode2R.right = treeNode1RRR;


        TreeNode treeNode1 = new TreeNode(Integer.MIN_VALUE);
        TreeNode treeNode1L = new TreeNode(Integer.MIN_VALUE);
//        TreeNode treeNode1R = new TreeNode(5);
//        TreeNode treeNode1LL = new TreeNode(-36 );
//        TreeNode treeNode1LR = new TreeNode(2);
//        TreeNode treeNode2L = new TreeNode(4);
//        TreeNode treeNode2R = new TreeNode(6);
//        TreeNode treeNode3R = new TreeNode(3);
        treeNode1.left = treeNode1L;
//        treeNode1.right = treeNode1R;
//        treeNode1L.left = treeNode1LL;
//        treeNode1L.right = treeNode1LR;
//        treeNode1R.right = treeNode2R;
//        treeNode1R.left = treeNode2L;
//        treeNode1LR.right = treeNode3R;
        List res = largestValues(treeNode1);
        System.out.println(res);
    }

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
}
